
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 2444. -- [Usaco2011 Open]焊接 -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>2444: [Usaco2011 Open]焊接</h2><span class=green>Time Limit: </span>3 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>13&nbsp;&nbsp;<span class=green>Solved: </span>6<br>[<a href='submitpage.php?id=2444'>Submit</a>][<a href='problemstatus.php?id=2444'>Status</a>][<a href='bbs.php?id=2444'>Discuss</a>]</center><h2>Description</h2><div class=content><p><span style="font-size: medium"><br />
奶牛们正在玩电线！他们学会了焊接：把两条电线连接起来，将某条的端点焊接到<br />
另一条的中间某个位置(注意：不能够将两条电线的端点焊接起来，即中间某个位置<br />
不包括端点)。当然，中间的同一个位置可以焊接多条电线。(并且焊接点必须为整数点，<br />
这个好像英文题面没说，我是这么理解的)<br />
<br />
奶牛们准备建造一个神奇的结构。它是一个N(1 &lt;= N &lt;= 50,000)个节点N-1条边的图，<br />
并且任意两个节点连通。每条边通过两个整数A,B来表示(1 &lt;= A &lt;=N; 1 &lt;= B &lt;= N; A != B)。<br />
<br />
奶牛们要从当地的店里买电线，然而，越长的电线就越贵，具体地：一条长度为L的电线<br />
的售价为L*L，并且，电线是不允许连接或者裁断的。<br />
<br />
给出奶牛准备建造的结构，请帮助奶牛们找出最小的花费。<br />
</span></p></div><h2>Input</h2><div class=content><p><br />
* 第一行: 一个整数 N<br />
<br />
* 第二到N行: 每行两个整数A,B描述一条边<br />
<br />
</p></div><h2>Output</h2><div class=content><p><br />
* 第一行：一个整数表示最小的花费，注意这个整数可能超过32位二进制数。<br />
</p></div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>6<br />
1 2<br />
1 3<br />
1 4<br />
1 5<br />
1 6<br />
<br />
<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>7<br />
<br />
OUTPUT DETAILS:<br />
<br />
由于每个节点都和1号节点相连，因此，我们只要购买1条长度为2的电线和3条长度为1的电线即可。<br />
总的花费为2 * 2 +1 * 1 + 1 * 1 + 1 * 1 = 7。<br />
<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=2444'>Submit</a>][<a href='problemstatus.php?id=2444'>Status</a>][<a href='bbs.php?id=2444'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
